package hufumancode;

import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        byte[] contentBytes = str.getBytes();
        System.out.println(contentBytes.length);

        List<Node> nodes = getNode(contentBytes);
        System.out.println(nodes);
        System.out.println("赫夫曼树");
        Node huffManTreeRoot = createHuffManTree(nodes);
        System.out.println("前序遍历");
        preOrder(huffManTreeRoot);

        System.out.println("生成对应的赫夫曼编码");
        HashMap<Byte, String> hashMap = getCodes(huffManTreeRoot);
        System.out.println("生成的" + hashMap);
    }

    //将字符串对应的byte[]数组 通过生成的赫夫曼编码表 返回一个赫夫曼编码压缩过的byte


    //生成赫夫曼树对应的赫夫曼编码 Map<Byte,String>

    //用来拼接路径
    static StringBuilder stringBuilder = new StringBuilder();
    //用来保存赫夫曼编码表
    static HashMap<Byte, String> huffmanCodes = new HashMap<>();


    //为了方便进行重载方法
    public static HashMap<Byte, String> getCodes(Node root) {
        if (root == null) {
            System.out.println("root为空不能进行");
            return null;
        }
        getCodes(root.left, "0", stringBuilder);
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 将传入的node结点的所有的叶子节点得到赫夫曼编码并放入到hashmap集合当中
     *
     * @param node          传入节点
     * @param code          路径 左子节点0 右子节点1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if (node != null) {
            if (node.data == null) { //非叶子节点
                //递归
                getCodes(node.left, "0", stringBuilder2);
                getCodes(node.right, "1", stringBuilder2);
            } else { //叶子节点
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }


    public static void preOrder(Node root) {
        if (root != null) {
            root.perOrder();
        } else {
            System.out.println("root为空");
        }
    }

    //将list转为赫夫曼树
    public static Node createHuffManTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序
            Collections.sort(nodes);
            //取出最小和第二最小的树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //创建一颗新的二叉树 根节点没有data 只有权值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;

            //删除已经处理的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            //加入到node
            nodes.add(parent);

        }
        //返回根节点
        return nodes.get(0);
    }

    public static List<Node> getNode(byte[] bytes) {
        ArrayList<Node> nodes = new ArrayList<>();
        //存储每个byte出现的次数
        HashMap<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        //把每一个键值对转成一个Node对象 并加入到nodes集合
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
}


class Node implements Comparable<Node> {
    Byte data; //存放数据本身
    int weight; //权值 表示出现的次数
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }


    public void perOrder() {
        System.out.println(this);
        if (this.left != null) {
            left.perOrder();
        }
        if (this.right != null) {
            right.perOrder();
        }
    }

    @Override
    public String toString() {
        return "Node [data=" + data + ",weight" + weight + "]";
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}